Now that we understand how to mathematically simplify the running time $f(n)$ down to its dominating term $O(f(n))$, we can directly compare the efficiency of different algorithms. This comparison is most intuitive when we visualize the cost $f(n)$ (y-axis) versus the input size $n$ (x-axis).
- Visualizing these growth curves clarifies why asymptotic analysis is so powerful: it provides an immediate assessment of an algorithm's scalability. When $n$ becomes large, the difference between a slightly better constant factor (e.g., $5n$ vs $10n$) is trivial compared to the difference in the fundamental growth rate (e.g., $O(n)$ vs $O(n^2)$).
- Efficient Growth (Scalable): Algorithms whose cost curves are flat or increase slowly. Examples: $O(1)$, $O(\log_2(n))$, $O(n)$.
- Inefficient Growth (Unscalable): Algorithms whose cost curves increase steeply, quickly becoming unusable for large $n$. Examples: $O(n^2)$, $O(n^3)$, $O(2^n)$.
- The transition from a linear search ($O(n)$) to a binary search ($O(\log_2(n))$) demonstrates a monumental shift in scalability, especially when $n$ represents inputs in the millions or billions.
Growth Rate Summary
| Complexity | Name | Scalability |
|---|---|---|
| $O(1)$ | Constant | Excellent |
| $O(\log n)$ | Logarithmic | Great |
| $O(n)$ | Linear | Good |
| $O(n^2)$ | Quadratic | Poor |
| $O(2^n)$ | Exponential | Terrible |